package com.cet.algorithm.二叉树.平衡二叉树;

/**
 * @program: algorithm
 * @description: 判断一个二叉树是否为平衡二叉树
 * @author: 陈恩涛
 * @create: 2022-07-21 14:59
 **/
public class LC110 {

    public static void main(String[] args) {
        // [1,2,2,3,3,null,null,4,4]
        final TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(3, new TreeNode(4), new TreeNode(4)), new TreeNode(3)), new TreeNode(2));
        System.out.println(new LC110().isBalanced(root));
    }

    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode node) {

        if (node == null) {
            return 0;
        }
        final int leftHeight = getHeight(node.left);
        if (leftHeight == -1) {
            return -1;
        }
        final int rightHeight = getHeight(node.right);
        if (rightHeight == -1) {
            return -1;
        }

        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return 1 + Math.max(leftHeight, rightHeight);
    }
}
